home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 22 / PCPP #22.iso / Quake2 / q2source_12_11 / utils3 / bsp / qbsp3 / brushbsp.c next >
Encoding:
C/C++ Source or Header  |  1997-11-19  |  23.6 KB  |  1,310 lines
  1.  
  2. #include "qbsp.h"
  3.  
  4.  
  5. int        c_nodes;
  6. int        c_nonvis;
  7. int        c_active_brushes;
  8.  
  9. // if a brush just barely pokes onto the other side,
  10. // let it slide by without chopping
  11. #define    PLANESIDE_EPSILON    0.001
  12. //0.1
  13.  
  14. #define    PSIDE_FRONT            1
  15. #define    PSIDE_BACK            2
  16. #define    PSIDE_BOTH            (PSIDE_FRONT|PSIDE_BACK)
  17. #define    PSIDE_FACING        4
  18.  
  19.  
  20. void FindBrushInTree (node_t *node, int brushnum)
  21. {
  22.     bspbrush_t    *b;
  23.  
  24.     if (node->planenum == PLANENUM_LEAF)
  25.     {
  26.         for (b=node->brushlist ; b ; b=b->next)
  27.             if (b->original->brushnum == brushnum)
  28.                 printf ("here\n");
  29.         return;
  30.     }
  31.     FindBrushInTree (node->children[0], brushnum);
  32.     FindBrushInTree (node->children[1], brushnum);
  33. }
  34.  
  35. //==================================================
  36.  
  37. /*
  38. ================
  39. DrawBrushList
  40. ================
  41. */
  42. void DrawBrushList (bspbrush_t *brush, node_t *node)
  43. {
  44.     int        i;
  45.     side_t    *s;
  46.  
  47.     GLS_BeginScene ();
  48.     for ( ; brush ; brush=brush->next)
  49.     {
  50.         for (i=0 ; i<brush->numsides ; i++)
  51.         {
  52.             s = &brush->sides[i];
  53.             if (!s->winding)
  54.                 continue;
  55.             if (s->texinfo == TEXINFO_NODE)
  56.                 GLS_Winding (s->winding, 1);
  57.             else if (!s->visible)
  58.                 GLS_Winding (s->winding, 2);
  59.             else
  60.                 GLS_Winding (s->winding, 0);
  61.         }
  62.     }
  63.     GLS_EndScene ();
  64. }
  65.  
  66. /*
  67. ================
  68. WriteBrushList
  69. ================
  70. */
  71. void WriteBrushList (char *name, bspbrush_t *brush, qboolean onlyvis)
  72. {
  73.     int        i;
  74.     side_t    *s;
  75.     FILE    *f;
  76.  
  77.     qprintf ("writing %s\n", name);
  78.     f = SafeOpenWrite (name);
  79.  
  80.     for ( ; brush ; brush=brush->next)
  81.     {
  82.         for (i=0 ; i<brush->numsides ; i++)
  83.         {
  84.             s = &brush->sides[i];
  85.             if (!s->winding)
  86.                 continue;
  87.             if (onlyvis && !s->visible)
  88.                 continue;
  89.             OutputWinding (brush->sides[i].winding, f);
  90.         }
  91.     }
  92.  
  93.     fclose (f);
  94. }
  95.  
  96. void PrintBrush (bspbrush_t *brush)
  97. {
  98.     int        i;
  99.  
  100.     printf ("brush: %p\n", brush);
  101.     for (i=0;i<brush->numsides ; i++)
  102.     {
  103.         pw(brush->sides[i].winding);
  104.         printf ("\n");
  105.     }
  106. }
  107.  
  108. /*
  109. ==================
  110. BoundBrush
  111.  
  112. Sets the mins/maxs based on the windings
  113. ==================
  114. */
  115. void BoundBrush (bspbrush_t *brush)
  116. {
  117.     int            i, j;
  118.     winding_t    *w;
  119.  
  120.     ClearBounds (brush->mins, brush->maxs);
  121.     for (i=0 ; i<brush->numsides ; i++)
  122.     {
  123.         w = brush->sides[i].winding;
  124.         if (!w)
  125.             continue;
  126.         for (j=0 ; j<w->numpoints ; j++)
  127.             AddPointToBounds (w->p[j], brush->mins, brush->maxs);
  128.     }
  129. }
  130.  
  131. /*
  132. ==================
  133. CreateBrushWindings
  134.  
  135. ==================
  136. */
  137. void CreateBrushWindings (bspbrush_t *brush)
  138. {
  139.     int            i, j;
  140.     winding_t    *w;
  141.     side_t        *side;
  142.     plane_t        *plane;
  143.  
  144.     for (i=0 ; i<brush->numsides ; i++)
  145.     {
  146.         side = &brush->sides[i];
  147.         plane = &mapplanes[side->planenum];
  148.         w = BaseWindingForPlane (plane->normal, plane->dist);
  149.         for (j=0 ; j<brush->numsides && w; j++)
  150.         {
  151.             if (i == j)
  152.                 continue;
  153.             if (brush->sides[j].bevel)
  154.                 continue;
  155.             plane = &mapplanes[brush->sides[j].planenum^1];
  156.             ChopWindingInPlace (&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);
  157.         }
  158.  
  159.         side->winding = w;
  160.     }
  161.  
  162.     BoundBrush (brush);
  163. }
  164.  
  165. /*
  166. ==================
  167. BrushFromBounds
  168.  
  169. Creates a new axial brush
  170. ==================
  171. */
  172. bspbrush_t    *BrushFromBounds (vec3_t mins, vec3_t maxs)
  173. {
  174.     bspbrush_t    *b;
  175.     int            i;
  176.     vec3_t        normal;
  177.     vec_t        dist;
  178.  
  179.     b = AllocBrush (6);
  180.     b->numsides = 6;
  181.     for (i=0 ; i<3 ; i++)
  182.     {
  183.         VectorClear (normal);
  184.         normal[i] = 1;
  185.         dist = maxs[i];
  186.         b->sides[i].planenum = FindFloatPlane (normal, dist);
  187.  
  188.         normal[i] = -1;
  189.         dist = -mins[i];
  190.         b->sides[3+i].planenum = FindFloatPlane (normal, dist);
  191.     }
  192.  
  193.     CreateBrushWindings (b);
  194.  
  195.     return b;
  196. }
  197.  
  198. /*
  199. ==================
  200. BrushVolume
  201.  
  202. ==================
  203. */
  204. vec_t BrushVolume (bspbrush_t *brush)
  205. {
  206.     int            i;
  207.     winding_t    *w;
  208.     vec3_t        corner;
  209.     vec_t        d, area, volume;
  210.     plane_t        *plane;
  211.  
  212.     if (!brush)
  213.         return 0;
  214.  
  215.     // grab the first valid point as the corner
  216.  
  217.     w = NULL;
  218.     for (i=0 ; i<brush->numsides ; i++)
  219.     {
  220.         w = brush->sides[i].winding;
  221.         if (w)
  222.             break;
  223.     }
  224.     if (!w)
  225.         return 0;
  226.     VectorCopy (w->p[0], corner);
  227.  
  228.     // make tetrahedrons to all other faces
  229.  
  230.     volume = 0;
  231.     for ( ; i<brush->numsides ; i++)
  232.     {
  233.         w = brush->sides[i].winding;
  234.         if (!w)
  235.             continue;
  236.         plane = &mapplanes[brush->sides[i].planenum];
  237.         d = -(DotProduct (corner, plane->normal) - plane->dist);
  238.         area = WindingArea (w);
  239.         volume += d*area;
  240.     }
  241.  
  242.     volume /= 3;
  243.     return volume;
  244. }
  245.  
  246. /*
  247. ================
  248. CountBrushList
  249. ================
  250. */
  251. int    CountBrushList (bspbrush_t *brushes)
  252. {
  253.     int    c;
  254.  
  255.     c = 0;
  256.     for ( ; brushes ; brushes = brushes->next)
  257.         c++;
  258.     return c;
  259. }
  260.  
  261. /*
  262. ================
  263. AllocTree
  264. ================
  265. */
  266. tree_t *AllocTree (void)
  267. {
  268.     tree_t    *tree;
  269.  
  270.     tree = malloc(sizeof(*tree));
  271.     memset (tree, 0, sizeof(*tree));
  272.     ClearBounds (tree->mins, tree->maxs);
  273.  
  274.     return tree;
  275. }
  276.  
  277. /*
  278. ================
  279. AllocNode
  280. ================
  281. */
  282. node_t *AllocNode (void)
  283. {
  284.     node_t    *node;
  285.  
  286.     node = malloc(sizeof(*node));
  287.     memset (node, 0, sizeof(*node));
  288.  
  289.     return node;
  290. }
  291.  
  292.  
  293. /*
  294. ================
  295. AllocBrush
  296. ================
  297. */
  298. bspbrush_t *AllocBrush (int numsides)
  299. {
  300.     bspbrush_t    *bb;
  301.     int            c;
  302.  
  303.     c = (int)&(((bspbrush_t *)0)->sides[numsides]);
  304.     bb = malloc(c);
  305.     memset (bb, 0, c);
  306.     if (numthreads == 1)
  307.         c_active_brushes++;
  308.     return bb;
  309. }
  310.  
  311. /*
  312. ================
  313. FreeBrush
  314. ================
  315. */
  316. void FreeBrush (bspbrush_t *brushes)
  317. {
  318.     int            i;
  319.  
  320.     for (i=0 ; i<brushes->numsides ; i++)
  321.         if (brushes->sides[i].winding)
  322.             FreeWinding(brushes->sides[i].winding);
  323.     free (brushes);
  324.     if (numthreads == 1)
  325.         c_active_brushes--;
  326. }
  327.  
  328.  
  329. /*
  330. ================
  331. FreeBrushList
  332. ================
  333. */
  334. void FreeBrushList (bspbrush_t *brushes)
  335. {
  336.     bspbrush_t    *next;
  337.  
  338.     for ( ; brushes ; brushes = next)
  339.     {
  340.         next = brushes->next;
  341.  
  342.         FreeBrush (brushes);
  343.     }        
  344. }
  345.  
  346. /*
  347. ==================
  348. CopyBrush
  349.  
  350. Duplicates the brush, the sides, and the windings
  351. ==================
  352. */
  353. bspbrush_t *CopyBrush (bspbrush_t *brush)
  354. {
  355.     bspbrush_t *newbrush;
  356.     int            size;
  357.     int            i;
  358.     
  359.     size = (int)&(((bspbrush_t *)0)->sides[brush->numsides]);
  360.  
  361.     newbrush = AllocBrush (brush->numsides);
  362.     memcpy (newbrush, brush, size);
  363.  
  364.     for (i=0 ; i<brush->numsides ; i++)
  365.     {
  366.         if (brush->sides[i].winding)
  367.             newbrush->sides[i].winding = CopyWinding (brush->sides[i].winding);
  368.     }
  369.  
  370.     return newbrush;
  371. }
  372.  
  373.  
  374. /*
  375. ==================
  376. PointInLeaf
  377.  
  378. ==================
  379. */
  380. node_t    *PointInLeaf (node_t *node, vec3_t point)
  381. {
  382.     vec_t        d;
  383.     plane_t        *plane;
  384.  
  385.     while (node->planenum != PLANENUM_LEAF)
  386.     {
  387.         plane = &mapplanes[node->planenum];
  388.         d = DotProduct (point, plane->normal) - plane->dist;
  389.         if (d > 0)
  390.             node = node->children[0];
  391.         else
  392.             node = node->children[1];
  393.     }
  394.  
  395.     return node;
  396. }
  397.  
  398. //========================================================
  399.  
  400. /*
  401. ==============
  402. BoxOnPlaneSide
  403.  
  404. Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH
  405. ==============
  406. */
  407. int BoxOnPlaneSide (vec3_t mins, vec3_t maxs, plane_t *plane)
  408. {
  409.     int        side;
  410.     int        i;
  411.     vec3_t    corners[2];
  412.     vec_t    dist1, dist2;
  413.  
  414.     // axial planes are easy
  415.     if (plane->type < 3)
  416.     {
  417.         side = 0;
  418.         if (maxs[plane->type] > plane->dist+PLANESIDE_EPSILON)
  419.             side |= PSIDE_FRONT;
  420.         if (mins[plane->type] < plane->dist-PLANESIDE_EPSILON)
  421.             side |= PSIDE_BACK;
  422.         return side;
  423.     }
  424.  
  425.     // create the proper leading and trailing verts for the box
  426.  
  427.     for (i=0 ; i<3 ; i++)
  428.     {
  429.         if (plane->normal[i] < 0)
  430.         {
  431.             corners[0][i] = mins[i];
  432.             corners[1][i] = maxs[i];
  433.         }
  434.         else
  435.         {
  436.             corners[1][i] = mins[i];
  437.             corners[0][i] = maxs[i];
  438.         }
  439.     }
  440.  
  441.     dist1 = DotProduct (plane->normal, corners[0]) - plane->dist;
  442.     dist2 = DotProduct (plane->normal, corners[1]) - plane->dist;
  443.     side = 0;
  444.     if (dist1 >= PLANESIDE_EPSILON)
  445.         side = PSIDE_FRONT;
  446.     if (dist2 < PLANESIDE_EPSILON)
  447.         side |= PSIDE_BACK;
  448.  
  449.     return side;
  450. }
  451.  
  452. /*
  453. ============
  454. QuickTestBrushToPlanenum
  455.  
  456. ============
  457. */
  458. int    QuickTestBrushToPlanenum (bspbrush_t *brush, int planenum, int *numsplits)
  459. {
  460.     int            i, num;
  461.     plane_t        *plane;
  462.     int            s;
  463.  
  464.     *numsplits = 0;
  465.  
  466.     // if the brush actually uses the planenum,
  467.     // we can tell the side for sure
  468.     for (i=0 ; i<brush->numsides ; i++)
  469.     {
  470.         num = brush->sides[i].planenum;
  471.         if (num >= 0x10000)
  472.             Error ("bad planenum");
  473.         if (num == planenum)
  474.             return PSIDE_BACK|PSIDE_FACING;
  475.         if (num == (planenum ^ 1) )
  476.             return PSIDE_FRONT|PSIDE_FACING;
  477.     }
  478.  
  479.     // box on plane side
  480.     plane = &mapplanes[planenum];
  481.     s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);
  482.  
  483.     // if both sides, count the visible faces split
  484.     if (s == PSIDE_BOTH)
  485.     {
  486.         *numsplits += 3;
  487.     }
  488.  
  489.     return s;
  490. }
  491.  
  492. /*
  493. ============
  494. TestBrushToPlanenum
  495.  
  496. ============
  497. */
  498. int    TestBrushToPlanenum (bspbrush_t *brush, int planenum,
  499.                          int *numsplits, qboolean *hintsplit, int *epsilonbrush)
  500. {
  501.     int            i, j, num;
  502.     plane_t        *plane;
  503.     int            s;
  504.     winding_t    *w;
  505.     vec_t        d, d_front, d_back;
  506.     int            front, back;
  507.  
  508.     *numsplits = 0;
  509.     *hintsplit = false;
  510.  
  511.     // if the brush actually uses the planenum,
  512.     // we can tell the side for sure
  513.     for (i=0 ; i<brush->numsides ; i++)
  514.     {
  515.         num = brush->sides[i].planenum;
  516.         if (num >= 0x10000)
  517.             Error ("bad planenum");
  518.         if (num == planenum)
  519.             return PSIDE_BACK|PSIDE_FACING;
  520.         if (num == (planenum ^ 1) )
  521.             return PSIDE_FRONT|PSIDE_FACING;
  522.     }
  523.  
  524.     // box on plane side
  525.     plane = &mapplanes[planenum];
  526.     s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);
  527.  
  528.     if (s != PSIDE_BOTH)
  529.         return s;
  530.  
  531. // if both sides, count the visible faces split
  532.     d_front = d_back = 0;
  533.  
  534.     for (i=0 ; i<brush->numsides ; i++)
  535.     {
  536.         if (brush->sides[i].texinfo == TEXINFO_NODE)
  537.             continue;        // on node, don't worry about splits
  538.         if (!brush->sides[i].visible)
  539.             continue;        // we don't care about non-visible
  540.         w = brush->sides[i].winding;
  541.         if (!w)
  542.             continue;
  543.         front = back = 0;
  544.         for (j=0 ; j<w->numpoints; j++)
  545.         {
  546.             d = DotProduct (w->p[j], plane->normal) - plane->dist;
  547.             if (d > d_front)
  548.                 d_front = d;
  549.             if (d < d_back)
  550.                 d_back = d;
  551.  
  552.             if (d > 0.1) // PLANESIDE_EPSILON)
  553.                 front = 1;
  554.             if (d < -0.1) // PLANESIDE_EPSILON)
  555.                 back = 1;
  556.         }
  557.         if (front && back)
  558.         {
  559.             if ( !(brush->sides[i].surf & SURF_SKIP) )
  560.             {
  561.                 (*numsplits)++;
  562.                 if (brush->sides[i].surf & SURF_HINT)
  563.                     *hintsplit = true;
  564.             }
  565.         }
  566.     }
  567.  
  568.     if ( (d_front > 0.0 && d_front < 1.0)
  569.         || (d_back < 0.0 && d_back > -1.0) )
  570.         (*epsilonbrush)++;
  571.  
  572. #if 0
  573.     if (*numsplits == 0)
  574.     {    //    didn't really need to be split
  575.         if (front)
  576.             s = PSIDE_FRONT;
  577.         else if (back)
  578.             s = PSIDE_BACK;
  579.         else
  580.             s = 0;
  581.     }
  582. #endif
  583.  
  584.     return s;
  585. }
  586.  
  587. //========================================================
  588.  
  589. /*
  590. ================
  591. WindingIsTiny
  592.  
  593. Returns true if the winding would be crunched out of
  594. existance by the vertex snapping.
  595. ================
  596. */
  597. #define    EDGE_LENGTH    0.2
  598. qboolean WindingIsTiny (winding_t *w)
  599. {
  600. #if 0
  601.     if (WindingArea (w) < 1)
  602.         return true;
  603.     return false;
  604. #else
  605.     int        i, j;
  606.     vec_t    len;
  607.     vec3_t    delta;
  608.     int        edges;
  609.  
  610.     edges = 0;
  611.     for (i=0 ; i<w->numpoints ; i++)
  612.     {
  613.         j = i == w->numpoints - 1 ? 0 : i+1;
  614.         VectorSubtract (w->p[j], w->p[i], delta);
  615.         len = VectorLength (delta);
  616.         if (len > EDGE_LENGTH)
  617.         {
  618.             if (++edges == 3)
  619.                 return false;
  620.         }
  621.     }
  622.     return true;
  623. #endif
  624. }
  625.  
  626. /*
  627. ================
  628. WindingIsHuge
  629.  
  630. Returns true if the winding still has one of the points
  631. from basewinding for plane
  632. ================
  633. */
  634. qboolean WindingIsHuge (winding_t *w)
  635. {
  636.     int        i, j;
  637.  
  638.     for (i=0 ; i<w->numpoints ; i++)
  639.     {
  640.         for (j=0 ; j<3 ; j++)
  641.             if (w->p[i][j] < -8000 || w->p[i][j] > 8000)
  642.                 return true;
  643.     }
  644.     return false;
  645. }
  646.  
  647. //============================================================
  648.  
  649. /*
  650. ================
  651. Leafnode
  652. ================
  653. */
  654. void LeafNode (node_t *node, bspbrush_t *brushes)
  655. {
  656.     bspbrush_t    *b;
  657.     int            i;
  658.  
  659.     node->planenum = PLANENUM_LEAF;
  660.     node->contents = 0;
  661.  
  662.     for (b=brushes ; b ; b=b->next)
  663.     {
  664.         // if the brush is solid and all of its sides are on nodes,
  665.         // it eats everything
  666.         if (b->original->contents & CONTENTS_SOLID)
  667.         {
  668.             for (i=0 ; i<b->numsides ; i++)
  669.                 if (b->sides[i].texinfo != TEXINFO_NODE)
  670.                     break;
  671.             if (i == b->numsides)
  672.             {
  673.                 node->contents = CONTENTS_SOLID;
  674.                 break;
  675.             }
  676.         }
  677.         node->contents |= b->original->contents;
  678.     }
  679.  
  680.     node->brushlist = brushes;
  681. }
  682.  
  683.  
  684. //============================================================
  685.  
  686. void CheckPlaneAgainstParents (int pnum, node_t *node)
  687. {
  688.     node_t    *p;
  689.  
  690.     for (p=node->parent ; p ; p=p->parent)
  691.     {
  692.         if (p->planenum == pnum)
  693.             Error ("Tried parent");
  694.     }
  695. }
  696.  
  697. qboolean CheckPlaneAgainstVolume (int pnum, node_t *node)
  698. {
  699.     bspbrush_t    *front, *back;
  700.     qboolean    good;
  701.  
  702.     SplitBrush (node->volume, pnum, &front, &back);
  703.  
  704.     good = (front && back);
  705.  
  706.     if (front)
  707.         FreeBrush (front);
  708.     if (back)
  709.         FreeBrush (back);
  710.  
  711.     return good;
  712. }
  713.  
  714. /*
  715. ================
  716. SelectSplitSide
  717.  
  718. Using a hueristic, choses one of the sides out of the brushlist
  719. to partition the brushes with.
  720. Returns NULL if there are no valid planes to split with..
  721. ================
  722. */
  723. side_t *SelectSplitSide (bspbrush_t *brushes, node_t *node)
  724. {
  725.     int            value, bestvalue;
  726.     bspbrush_t    *brush, *test;
  727.     side_t        *side, *bestside;
  728.     int            i, j, pass, numpasses;
  729.     int            pnum;
  730.     int            s;
  731.     int            front, back, both, facing, splits;
  732.     int            bsplits;
  733.     int            bestsplits;
  734.     int            epsilonbrush;
  735.     qboolean    hintsplit;
  736.  
  737.     bestside = NULL;
  738.     bestvalue = -99999;
  739.     bestsplits = 0;
  740.  
  741.     // the search order goes: visible-structural, visible-detail,
  742.     // nonvisible-structural, nonvisible-detail.
  743.     // If any valid plane is available in a pass, no further
  744.     // passes will be tried.
  745.     numpasses = 4;
  746.     for (pass = 0 ; pass < numpasses ; pass++)
  747.     {
  748.         for (brush = brushes ; brush ; brush=brush->next)
  749.         {
  750.             if ( (pass & 1) && !(brush->original->contents & CONTENTS_DETAIL) )
  751.                 continue;
  752.             if ( !(pass & 1) && (brush->original->contents & CONTENTS_DETAIL) )
  753.                 continue;
  754.             for (i=0 ; i<brush->numsides ; i++)
  755.             {
  756.                 side = brush->sides + i;
  757.                 if (side->bevel)
  758.                     continue;    // never use a bevel as a spliter
  759.                 if (!side->winding)
  760.                     continue;    // nothing visible, so it can't split
  761.                 if (side->texinfo == TEXINFO_NODE)
  762.                     continue;    // allready a node splitter
  763.                 if (side->tested)
  764.                     continue;    // we allready have metrics for this plane
  765.                 if (side->surf & SURF_SKIP)
  766.                     continue;    // skip surfaces are never chosen
  767.                 if ( side->visible ^ (pass<2) )
  768.                     continue;    // only check visible faces on first pass
  769.  
  770.                 pnum = side->planenum;
  771.                 pnum &= ~1;    // allways use positive facing plane
  772.  
  773.                 CheckPlaneAgainstParents (pnum, node);
  774.  
  775.                 if (!CheckPlaneAgainstVolume (pnum, node))
  776.                     continue;    // would produce a tiny volume
  777.  
  778.                 front = 0;
  779.                 back = 0;
  780.                 both = 0;
  781.                 facing = 0;
  782.                 splits = 0;
  783.                 epsilonbrush = 0;
  784.  
  785.                 for (test = brushes ; test ; test=test->next)
  786.                 {
  787.                     s = TestBrushToPlanenum (test, pnum, &bsplits, &hintsplit, &epsilonbrush);
  788.  
  789.                     splits += bsplits;
  790.                     if (bsplits && (s&PSIDE_FACING) )
  791.                         Error ("PSIDE_FACING with splits");
  792.  
  793.                     test->testside = s;
  794.                     // if the brush shares this face, don't bother
  795.                     // testing that facenum as a splitter again
  796.                     if (s & PSIDE_FACING)
  797.                     {
  798.                         facing++;
  799.                         for (j=0 ; j<test->numsides ; j++)
  800.                         {
  801.                             if ( (test->sides[j].planenum&~1) == pnum)
  802.                                 test->sides[j].tested = true;
  803.                         }
  804.                     }
  805.                     if (s & PSIDE_FRONT)
  806.                         front++;
  807.                     if (s & PSIDE_BACK)
  808.                         back++;
  809.                     if (s == PSIDE_BOTH)
  810.                         both++;
  811.                 }
  812.  
  813.                 // give a value estimate for using this plane
  814.  
  815.                 value =  5*facing - 5*splits - abs(front-back);
  816. //                    value =  -5*splits;
  817. //                    value =  5*facing - 5*splits;
  818.                 if (mapplanes[pnum].type < 3)
  819.                     value+=5;        // axial is better
  820.                 value -= epsilonbrush*1000;    // avoid!
  821.  
  822.                 // never split a hint side except with another hint
  823.                 if (hintsplit && !(side->surf & SURF_HINT) )
  824.                     value = -9999999;
  825.  
  826.                 // save off the side test so we don't need
  827.                 // to recalculate it when we actually seperate
  828.                 // the brushes
  829.                 if (value > bestvalue)
  830.                 {
  831.                     bestvalue = value;
  832.                     bestside = side;
  833.                     bestsplits = splits;
  834.                     for (test = brushes ; test ; test=test->next)
  835.                         test->side = test->testside;
  836.                 }
  837.             }
  838.         }
  839.  
  840.         // if we found a good plane, don't bother trying any
  841.         // other passes
  842.         if (bestside)
  843.         {
  844.             if (pass > 1)
  845.             {
  846.                 if (numthreads == 1)
  847.                     c_nonvis++;
  848.             }
  849.             if (pass > 0)
  850.                 node->detail_seperator = true;    // not needed for vis
  851.             break;
  852.         }
  853.     }
  854.  
  855.     //
  856.     // clear all the tested flags we set
  857.     //
  858.     for (brush = brushes ; brush ; brush=brush->next)
  859.     {
  860.         for (i=0 ; i<brush->numsides ; i++)
  861.             brush->sides[i].tested = false;
  862.     }
  863.  
  864.     return bestside;
  865. }
  866.  
  867.  
  868. /*
  869. ==================
  870. BrushMostlyOnSide
  871.  
  872. ==================
  873. */
  874. int BrushMostlyOnSide (bspbrush_t *brush, plane_t *plane)
  875. {
  876.     int            i, j;
  877.     winding_t    *w;
  878.     vec_t        d, max;
  879.     int            side;
  880.  
  881.     max = 0;
  882.     side = PSIDE_FRONT;
  883.     for (i=0 ; i<brush->numsides ; i++)
  884.     {
  885.         w = brush->sides[i].winding;
  886.         if (!w)
  887.             continue;
  888.         for (j=0 ; j<w->numpoints ; j++)
  889.         {
  890.             d = DotProduct (w->p[j], plane->normal) - plane->dist;
  891.             if (d > max)
  892.             {
  893.                 max = d;
  894.                 side = PSIDE_FRONT;
  895.             }
  896.             if (-d > max)
  897.             {
  898.                 max = -d;
  899.                 side = PSIDE_BACK;
  900.             }
  901.         }
  902.     }
  903.     return side;
  904. }
  905.  
  906. /*
  907. ================
  908. SplitBrush
  909.  
  910. Generates two new brushes, leaving the original
  911. unchanged
  912. ================
  913. */
  914. void SplitBrush (bspbrush_t *brush, int planenum,
  915.     bspbrush_t **front, bspbrush_t **back)
  916. {
  917.     bspbrush_t    *b[2];
  918.     int            i, j;
  919.     winding_t    *w, *cw[2], *midwinding;
  920.     plane_t        *plane, *plane2;
  921.     side_t        *s, *cs;
  922.     float        d, d_front, d_back;
  923.  
  924.     *front = *back = NULL;
  925.     plane = &mapplanes[planenum];
  926.  
  927.     // check all points
  928.     d_front = d_back = 0;
  929.     for (i=0 ; i<brush->numsides ; i++)
  930.     {
  931.         w = brush->sides[i].winding;
  932.         if (!w)
  933.             continue;
  934.         for (j=0 ; j<w->numpoints ; j++)
  935.         {
  936.             d = DotProduct (w->p[j], plane->normal) - plane->dist;
  937.             if (d > 0 && d > d_front)
  938.                 d_front = d;
  939.             if (d < 0 && d < d_back)
  940.                 d_back = d;
  941.         }
  942.     }
  943.     if (d_front < 0.1) // PLANESIDE_EPSILON)
  944.     {    // only on back
  945.         *back = CopyBrush (brush);
  946.         return;
  947.     }
  948.     if (d_back > -0.1) // PLANESIDE_EPSILON)
  949.     {    // only on front
  950.         *front = CopyBrush (brush);
  951.         return;
  952.     }
  953.  
  954.     // create a new winding from the split plane
  955.  
  956.     w = BaseWindingForPlane (plane->normal, plane->dist);
  957.     for (i=0 ; i<brush->numsides && w ; i++)
  958.     {
  959.         plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
  960.         ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
  961.     }
  962.  
  963.     if (!w || WindingIsTiny (w) )
  964.     {    // the brush isn't really split
  965.         int        side;
  966.  
  967.         side = BrushMostlyOnSide (brush, plane);
  968.         if (side == PSIDE_FRONT)
  969.             *front = CopyBrush (brush);
  970.         if (side == PSIDE_BACK)
  971.             *back = CopyBrush (brush);
  972.         return;
  973.     }
  974.  
  975.     if (WindingIsHuge (w))
  976.     {
  977.         qprintf ("WARNING: huge winding\n");
  978.     }
  979.  
  980.     midwinding = w;
  981.  
  982.     // split it for real
  983.  
  984.     for (i=0 ; i<2 ; i++)
  985.     {
  986.         b[i] = AllocBrush (brush->numsides+1);
  987.         b[i]->original = brush->original;
  988.     }
  989.  
  990.     // split all the current windings
  991.  
  992.     for (i=0 ; i<brush->numsides ; i++)
  993.     {
  994.         s = &brush->sides[i];
  995.         w = s->winding;
  996.         if (!w)
  997.             continue;
  998.         ClipWindingEpsilon (w, plane->normal, plane->dist,
  999.             0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
  1000.         for (j=0 ; j<2 ; j++)
  1001.         {
  1002.             if (!cw[j])
  1003.                 continue;
  1004. #if 0
  1005.             if (WindingIsTiny (cw[j]))
  1006.             {
  1007.                 FreeWinding (cw[j]);
  1008.                 continue;
  1009.             }
  1010. #endif
  1011.             cs = &b[j]->sides[b[j]->numsides];
  1012.             b[j]->numsides++;
  1013.             *cs = *s;
  1014. //            cs->planenum = s->planenum;
  1015. //            cs->texinfo = s->texinfo;
  1016. //            cs->visible = s->visible;
  1017. //            cs->original = s->original;
  1018.             cs->winding = cw[j];
  1019.             cs->tested = false;
  1020.         }
  1021.     }
  1022.  
  1023.  
  1024.     // see if we have valid polygons on both sides
  1025.  
  1026.     for (i=0 ; i<2 ; i++)
  1027.     {
  1028.         BoundBrush (b[i]);
  1029.         for (j=0 ; j<3 ; j++)
  1030.         {
  1031.             if (b[i]->mins[j] < -4096 || b[i]->maxs[j] > 4096)
  1032.             {
  1033.                 qprintf ("bogus brush after clip\n");
  1034.                 break;
  1035.             }
  1036.         }
  1037.  
  1038.         if (b[i]->numsides < 3 || j < 3)
  1039.         {
  1040.             FreeBrush (b[i]);
  1041.             b[i] = NULL;
  1042.         }
  1043.     }
  1044.  
  1045.     if ( !(b[0] && b[1]) )
  1046.     {
  1047.         if (!b[0] && !b[1])
  1048.             qprintf ("split removed brush\n");
  1049.         else
  1050.             qprintf ("split not on both sides\n");
  1051.         if (b[0])
  1052.         {
  1053.             FreeBrush (b[0]);
  1054.             *front = CopyBrush (brush);
  1055.         }
  1056.         if (b[1])
  1057.         {
  1058.             FreeBrush (b[1]);
  1059.             *back = CopyBrush (brush);
  1060.         }
  1061.         return;
  1062.     }
  1063.  
  1064.     // add the midwinding to both sides
  1065.     for (i=0 ; i<2 ; i++)
  1066.     {
  1067.         cs = &b[i]->sides[b[i]->numsides];
  1068.         b[i]->numsides++;
  1069.  
  1070.         cs->planenum = planenum^i^1;
  1071.         cs->texinfo = TEXINFO_NODE;
  1072.         cs->visible = false;
  1073.         cs->tested = false;
  1074.         if (i==0)
  1075.             cs->winding = CopyWinding (midwinding);
  1076.         else
  1077.             cs->winding = midwinding;
  1078.     }
  1079.  
  1080. {
  1081.     vec_t    v1;
  1082.     int        i;
  1083.  
  1084.     for (i=0 ; i<2 ; i++)
  1085.     {
  1086.         v1 = BrushVolume (b[i]);
  1087.         if (v1 < 1.0)
  1088.         {
  1089.             FreeBrush (b[i]);
  1090.             b[i] = NULL;
  1091. //            qprintf ("tiny volume after clip\n");
  1092.         }
  1093.     }
  1094. }
  1095.  
  1096.     *front = b[0];
  1097.     *back = b[1];
  1098. }
  1099.  
  1100. /*
  1101. ================
  1102. SplitBrushList
  1103. ================
  1104. */
  1105. void SplitBrushList (bspbrush_t *brushes, 
  1106.     node_t *node, bspbrush_t **front, bspbrush_t **back)
  1107. {
  1108.     bspbrush_t    *brush, *newbrush, *newbrush2;
  1109.     side_t        *side;
  1110.     int            sides;
  1111.     int            i;
  1112.  
  1113.     *front = *back = NULL;
  1114.  
  1115.     for (brush = brushes ; brush ; brush=brush->next)
  1116.     {
  1117.         sides = brush->side;
  1118.  
  1119.         if (sides == PSIDE_BOTH)
  1120.         {    // split into two brushes
  1121.             SplitBrush (brush, node->planenum, &newbrush, &newbrush2);
  1122.             if (newbrush)
  1123.             {
  1124.                 newbrush->next = *front;
  1125.                 *front = newbrush;
  1126.             }
  1127.             if (newbrush2)
  1128.             {
  1129.                 newbrush2->next = *back;
  1130.                 *back = newbrush2;
  1131.             }
  1132.             continue;
  1133.         }
  1134.  
  1135.         newbrush = CopyBrush (brush);
  1136.  
  1137.         // if the planenum is actualy a part of the brush
  1138.         // find the plane and flag it as used so it won't be tried
  1139.         // as a splitter again
  1140.         if (sides & PSIDE_FACING)
  1141.         {
  1142.             for (i=0 ; i<newbrush->numsides ; i++)
  1143.             {
  1144.                 side = newbrush->sides + i;
  1145.                 if ( (side->planenum& ~1) == node->planenum)
  1146.                     side->texinfo = TEXINFO_NODE;
  1147.             }
  1148.         }
  1149.  
  1150.  
  1151.         if (sides & PSIDE_FRONT)
  1152.         {
  1153.             newbrush->next = *front;
  1154.             *front = newbrush;
  1155.             continue;
  1156.         }
  1157.         if (sides & PSIDE_BACK)
  1158.         {
  1159.             newbrush->next = *back;
  1160.             *back = newbrush;
  1161.             continue;
  1162.         }
  1163.     }
  1164. }
  1165.  
  1166.  
  1167. /*
  1168. ================
  1169. BuildTree_r
  1170. ================
  1171. */
  1172. node_t *BuildTree_r (node_t *node, bspbrush_t *brushes)
  1173. {
  1174.     node_t        *newnode;
  1175.     side_t        *bestside;
  1176.     int            i;
  1177.     bspbrush_t    *children[2];
  1178.  
  1179.     if (numthreads == 1)
  1180.         c_nodes++;
  1181.  
  1182.     if (drawflag)
  1183.         DrawBrushList (brushes, node);
  1184.  
  1185.     // find the best plane to use as a splitter
  1186.     bestside = SelectSplitSide (brushes, node);
  1187.     if (!bestside)
  1188.     {
  1189.         // leaf node
  1190.         node->side = NULL;
  1191.         node->planenum = -1;
  1192.         LeafNode (node, brushes);
  1193.         return node;
  1194.     }
  1195.  
  1196.     // this is a splitplane node
  1197.     node->side = bestside;
  1198.     node->planenum = bestside->planenum & ~1;    // always use front facing
  1199.  
  1200.     SplitBrushList (brushes, node, &children[0], &children[1]);
  1201.     FreeBrushList (brushes);
  1202.  
  1203.     // allocate children before recursing
  1204.     for (i=0 ; i<2 ; i++)
  1205.     {
  1206.         newnode = AllocNode ();
  1207.         newnode->parent = node;
  1208.         node->children[i] = newnode;
  1209.     }
  1210.  
  1211.     SplitBrush (node->volume, node->planenum, &node->children[0]->volume,
  1212.         &node->children[1]->volume);
  1213.  
  1214.     // recursively process children
  1215.     for (i=0 ; i<2 ; i++)
  1216.     {
  1217.         node->children[i] = BuildTree_r (node->children[i], children[i]);
  1218.     }
  1219.  
  1220.     return node;
  1221. }
  1222.  
  1223. //===========================================================
  1224.  
  1225. /*
  1226. =================
  1227. BrushBSP
  1228.  
  1229. The incoming list will be freed before exiting
  1230. =================
  1231. */
  1232. tree_t *BrushBSP (bspbrush_t *brushlist, vec3_t mins, vec3_t maxs)
  1233. {
  1234.     node_t        *node;
  1235.     bspbrush_t    *b;
  1236.     int            c_faces, c_nonvisfaces;
  1237.     int            c_brushes;
  1238.     tree_t        *tree;
  1239.     int            i;
  1240.     vec_t        volume;
  1241.  
  1242.     qprintf ("--- BrushBSP ---\n");
  1243.  
  1244.     tree = AllocTree ();
  1245.  
  1246.     c_faces = 0;
  1247.     c_nonvisfaces = 0;
  1248.     c_brushes = 0;
  1249.     for (b=brushlist ; b ; b=b->next)
  1250.     {
  1251.         c_brushes++;
  1252.  
  1253.         volume = BrushVolume (b);
  1254.         if (volume < microvolume)
  1255.         {
  1256.             printf ("WARNING: entity %i, brush %i: microbrush\n",
  1257.                 b->original->entitynum, b->original->brushnum);
  1258.         }
  1259.  
  1260.         for (i=0 ; i<b->numsides ; i++)
  1261.         {
  1262.             if (b->sides[i].bevel)
  1263.                 continue;
  1264.             if (!b->sides[i].winding)
  1265.                 continue;
  1266.             if (b->sides[i].texinfo == TEXINFO_NODE)
  1267.                 continue;
  1268.             if (b->sides[i].visible)
  1269.                 c_faces++;
  1270.             else
  1271.                 c_nonvisfaces++;
  1272.         }
  1273.  
  1274.         AddPointToBounds (b->mins, tree->mins, tree->maxs);
  1275.         AddPointToBounds (b->maxs, tree->mins, tree->maxs);
  1276.     }
  1277.  
  1278.     qprintf ("%5i brushes\n", c_brushes);
  1279.     qprintf ("%5i visible faces\n", c_faces);
  1280.     qprintf ("%5i nonvisible faces\n", c_nonvisfaces);
  1281.  
  1282.     c_nodes = 0;
  1283.     c_nonvis = 0;
  1284.     node = AllocNode ();
  1285.  
  1286.     node->volume = BrushFromBounds (mins, maxs);
  1287.  
  1288.     tree->headnode = node;
  1289.  
  1290.     node = BuildTree_r (node, brushlist);
  1291.     qprintf ("%5i visible nodes\n", c_nodes/2 - c_nonvis);
  1292.     qprintf ("%5i nonvis nodes\n", c_nonvis);
  1293.     qprintf ("%5i leafs\n", (c_nodes+1)/2);
  1294. #if 0
  1295. {    // debug code
  1296. static node_t    *tnode;
  1297. vec3_t    p;
  1298.  
  1299. p[0] = -1469;
  1300. p[1] = -118;
  1301. p[2] = 119;
  1302. tnode = PointInLeaf (tree->headnode, p);
  1303. printf ("contents: %i\n", tnode->contents);
  1304. p[0] = 0;
  1305. }
  1306. #endif
  1307.     return tree;
  1308. }
  1309.  
  1310.